/*
 * BackwardNondeterministicDawgMatching.cpp
 *
 *  Created on: 02-09-2013
 *      Author: Krzychu
 */

#include "BackwardNondeterministicDawgMatching.h"

#include "../Structures/Config.h"

#define ASIZE 255

BackwardNondeterministicDawgMatching::BackwardNondeterministicDawgMatching()
{

}

BackwardNondeterministicDawgMatching::~BackwardNondeterministicDawgMatching()
{

}

std::string BackwardNondeterministicDawgMatching::getName()
{
	return "BNDM";
}

searchResult BackwardNondeterministicDawgMatching::execute(std::string text,
		std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	int* B = new int[ASIZE];
	int d, i, last;

	/* Pre processing */
	int s = 1;
	for (i = patternSize - 1; i >= 0; i--)
	{
		B[pattern[i]] |= s;
		s <<= 1;
	}

	/* Searching phase */
	int j = 0;
	while (j <= textSize - patternSize)
	{
		result.iterationsTaken++;

		i = patternSize - 1;
		last = patternSize;
		d = ~0;
		while (i >= 0 && d != 0)
		{
			d &= B[text[j + i]];
			i--;
			if (d != 0)
			{
				if (i >= 0)
				{
					last = i + 1;
				}
				else
				{
					result.positionsFound.push_back(j);
					if (Config::getInstance()->getFindOneOccurence())
					{
						return result;
					}
				}
			}
			d <<= 1;
		}
		j += last;
	}

	return result;
}

